package elementary_alg.array;

import java.util.*;

/**
 * @author : Kong Decheng
 * @date : 2021/04/02
 * @description: 两个数组的交集 II
 */
public class LC6 {
    /**
     * 排序数组，双指针法
     *
     * @param nums_1
     * @param nums_2
     * @return
     */
    public int[] solution_1(int[] nums_1, int[] nums_2) {
        // 对数组进行排序
        Arrays.sort(nums_1);
        Arrays.sort(nums_2);
        int left = 0;
        int right = 0;
        // 交集结果集
        List<Integer> list = new ArrayList<>();
        // 有一个数组遍历完成则停止比较
        while (left < nums_1.length && right < nums_2.length) {
            if (nums_1[left] == nums_2[right]) {
                // 如果元素相等，则放到交集中
                list.add(nums_1[left]);
                right++;
                left++;
            } else if (nums_1[left] > nums_2[right]) {
                // 如果左边大于右边，说明此元素不是共有元素，则将右边继续移动，再次比较
                right++;
            } else {
                // 反之，移动左边
                left++;
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    /**
     * 使用 map
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] solution_2(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();

        // 1. 把 nums1 的元素放到 map 中
        // key = 元素 value = 元素出现的次数
        for (int i : nums1) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        // 2. 遍历 nums2
        for (int i : nums2) {
            // 查看 map 中是否包含该元素
            if (map.getOrDefault(i, 0) > 0) {
                // 如果包含，就把当前值加入到 list 中，
                list.add(i);
                // 再把出现次数减 1
                map.put(i, map.get(i) - 1);
            }
        }

        // 3. 把 list 转为数组
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}
